package top;

/**
 * @author chenyw
 * @date 2022/6/18 9:59
 * @description     KMP算法
 */
public class Top28strStr {
    public int strStr(String ss, String pp) {
        if(pp == null || pp.length() == 0){
            return 0;
        }
        int n = ss.length();
        int m = pp.length();
        ss = " " + ss;
        pp = " " + pp;

        char[] s = ss.toCharArray();
        char[] p = pp.toCharArray();

        int[] next = new int[m+1];
        //构建next数组
        for (int i = 2,j = 0; i <= m; i++) {
            while (j>0 && p[i]!=p[j+1]) {
                j = next[j];
            }
            if (p[i] == p[j+1]) {
                j++;
            }
            next[i] = j;
        }

        //开始匹配
        for (int i = 1,j = 0; i <= n; i++) {
            //匹配不成功， j = next[j]
            while (j > 0 && s[i] != p[j+1]){
                j = next[j];
            }
            //匹配成功的话，本次循环就j++，i++
            if(s[i] == p[j+1]) {
                j++;
            }
            if(j == m) {
                return i - m;
            }
        }
        return -1;
    }
}
